package top.ivansong92.example.leetcode.learning.data.struct.dic;


import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class TestExample1 {
    /**
     * 242. 有效的字母异位词
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s == null && t == null) {
            return true;
        } else if (s == null || t == null) {
            return false;
        } else if (s.length() != t.length()) {
            return false;
        }

        Map<Character, AtomicInteger> chMap = new HashMap<>();
        for (char ch : s.toCharArray()) {
            AtomicInteger atomicInteger = chMap.computeIfAbsent(ch, e -> new AtomicInteger(0));
            atomicInteger.addAndGet(1);
        }

        for (char ch : t.toCharArray()) {
            AtomicInteger val = chMap.get(ch);
            if (val == null || val.get() == 0) {
                return false;
            }
            val.addAndGet(-1);
        }
        return true;
    }


    public boolean isAnagramV2(String s, String t) {
        if (s == null && t == null) {
            return true;
        } else if (s == null || t == null) {
            return false;
        } else if (s.length() != t.length()) {
            return false;
        }

        int[] charCounter = new int[26];
        for (char ch : s.toCharArray()) {
            charCounter[ch - 'a']++;
        }

        for (char ch : t.toCharArray()) {
            int val = ch - 'a';
            if (charCounter[val] <= 0) {
                return false;
            }
            charCounter[val]--;
        }
        return true;
    }


    /**
     * 451. 根据字符出现频率排序
     * @param s
     * @return
     */
    public String frequencySort(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        //使用AtomicInteger的目的是只存一次map
        Map<Character, AtomicInteger> chMap = new HashMap<>(s.length());
        for (char ch : s.toCharArray()) {
            AtomicInteger atomicInteger = chMap.computeIfAbsent(ch, e -> new AtomicInteger(0));
            atomicInteger.addAndGet(1);
        }

        char[] newChars = new char[s.length()];
        int index = 0;
        for (Map.Entry<Character, AtomicInteger> entry : chMap.entrySet()
                .stream()
                .sorted((e1, e2) -> e2.getValue().get() - e1.getValue().get())
                .collect(Collectors.toList())) {
            char ch = entry.getKey();
            for (int i = 0; i < entry.getValue().get(); i++) {
                newChars[index++] = ch;
            }
        }
        return new String(newChars);
    }


    /**
     * 454. 四数相加 II
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        if (nums1.length == 1 && nums2.length == 1 && nums3.length == 1 && nums4.length == 1) {
            return nums1[0] + nums2[0] + nums3[0] + nums4[0] == 0 ? 1 : 0;
        }

        Map<Integer, AtomicInteger> mergeMap = new HashMap<>();
        for (int n1 : nums1) {
            for (int n2 : nums2) {
                int val = n1 + n2;
                AtomicInteger count = mergeMap.computeIfAbsent(val, e-> new AtomicInteger(0));
                count.addAndGet(1);
            }
        }

        int res = 0;
        for (int n3 : nums3) {
            for (int n4 : nums4) {
                int val = -(n3 + n4);
                AtomicInteger count = mergeMap.get(val);
                if (count == null) {
                    continue;
                }
                res += count.get();
            }
        }
        return res;
    }


    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return Collections.emptyList();
        }

        Map<String, List<String>> resultMap = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> val = resultMap.computeIfAbsent(key, e -> new ArrayList<>());
            val.add(str);
        }
        return new ArrayList<>(resultMap.values());
    }

    private static Map<Character, List<Character>> LETTER_MAP = new HashMap<>();

    static {
        LETTER_MAP.put('2', Arrays.asList('a', 'b', 'c'));
        LETTER_MAP.put('3', Arrays.asList('d', 'e', 'f'));
        LETTER_MAP.put('4', Arrays.asList('g', 'h', 'i'));
        LETTER_MAP.put('5', Arrays.asList('j', 'k', 'l'));
        LETTER_MAP.put('6', Arrays.asList('m', 'n', 'o'));
        LETTER_MAP.put('7', Arrays.asList('p', 'q', 'r', 's'));
        LETTER_MAP.put('8', Arrays.asList('t', 'u', 'v'));
        LETTER_MAP.put('9', Arrays.asList('w', 'x', 'y', 'z'));

    }

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }
        List<String> res = new ArrayList<>();
        doCombineLetter(digits, 0, "", res);
        return res;
    }

    private void doCombineLetter(String digits, int index, String parent, List<String> list) {
        if (index == digits.length()) {
            list.add(parent);
            return;
        }
        char ch = digits.charAt(index);
        List<Character> characters = LETTER_MAP.get(ch);
        if (characters == null) {
            return;
        }

        int next = index + 1;
        for (Character val : characters) {
            doCombineLetter(digits, next, parent + val.toString(), list);
        }
    }

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() < 4) {
            return Collections.emptyList();
        }
        List<String> res = new ArrayList<>();
        doSplitStringToIp(s, 0, new ArrayList<>(),  res);
        return res;
    }
    private void doSplitStringToIp(String ipStr, int index, List<String> parent, List<String> s) {
        if (parent.size() == 3) {
            if (index >= ipStr.length()) {
                return;
            }
            String sub = ipStr.substring(index);
            if (matchIpSub(sub)) {
                parent.add(sub);
                s.add(String.join(".", parent));
            }
            return;
        }
        List<String> newParent;
        for(int i = index + 1; i <= ipStr.length() && i <= index + 3; i ++) {
            String sub = ipStr.substring(index, i);
            if (matchIpSub(sub)) {
                newParent = new ArrayList<>(parent);
                newParent.add(sub);
                doSplitStringToIp(ipStr, i, newParent, s);
            }
        }
    }

    private boolean matchIpSub(String sub) {
        int len = sub.length();
        if (len == 0 || len > 3) {
            return false;
        }
        if (len == 3) {
            if (sub.startsWith("0")) {
                return false;
            }
            return Integer.parseInt(sub) <= 255;
        } else if (len == 2) {
            return !sub.startsWith("0");
        }
        return true;
    }
}
